package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.*;

/**
 * 普利姆算法和克鲁斯卡尔算法生成最小路径图
 */
public class PrimAndKruskalAlgorithm {
	
	@Test
	//普利姆算法生成最小路径图
	public void test1(){
		//创建一个图
		char[] data = new char[]{'A','B','C','D','E','F','G'};
		//创建邻接矩阵
		int[][] weight = new int[][]{
				{0,5,7,0,0,0,2},
				{5,0,0,9,0,0,3},
				{7,0,0,0,8,0,0},
				{0,9,0,0,0,4,0},
				{0,0,8,0,0,5,4},
				{0,5,7,4,5,0,6},
				{2,3,0,0,4,6,0}
		};
		//创建图
		MGraph graph = new MGraph(7, data, weight);
		graph.list();
		graph.createPrimMinGraph(1).list();
	}
	
	@Test
	//克鲁斯卡尔算法生成最小路径图
	public void test2(){
		//创建一个图
		char[] data = new char[]{'A','B','C','D','E','F','G'};
		//创建邻接矩阵
		int[][] weight = new int[][]{
				{ 0,12, 0, 0, 0,16,14},
				{12, 0,10, 0, 0, 7, 0},
				{ 0,10, 0, 8, 5, 6, 0},
				{ 0, 0, 8, 0, 9, 0, 0},
				{ 0, 0, 5, 9, 0, 2, 3},
				{16, 7, 6, 0, 2, 0, 4},
				{14, 0, 0, 0, 3, 4, 0}
		};
		//创建图
		MGraph graph = new MGraph(7, data, weight);
		graph.list();
		graph.createKruskalMinGraph();
	}
	
	class MGraph{
		int verx;//代表节点的个数
		char[] data;//顶点的值
		int[][] weight;//图的边,也就是邻接矩阵
		
		//构造方法
		public MGraph(int verx,char[] data,int[][] weight){
			this.verx = verx;
			this.data = data;
			this.weight = weight;
		}
		
		//遍历图
		public void list(){
			Arrays.stream(weight).forEach(a -> System.out.println(Arrays.toString(a)));
		}
		
		//普利姆算法生成最小路径图,start表示从哪个节点开始寻找最短路径
		public MGraph createPrimMinGraph(int start){
			//创建一个数组,标记哪些节点已读,0表示未读,1表示已读
			int[] visited = new int[verx];
			//创建一个新的图
			int[][] newGraph = new int[verx][verx];
			//将start设置为已读
			visited[start] = 1;
			//定义一个指针,minX指向节点的X坐标,minY指向节点Y坐标
			int minX = -1;
			int minY = -1;
			//
			//这里循环是每循环一次创建一条路,共创建verx - 1条
			for (int a = 1 ; a < verx ; a ++){
				//对min每次循环赋初始值
				minX = -1;
				minY = -1;
				//遍历已读的集合,根据已读节点查找它邻接节点的最小路径节点
				for (int s = 0; s < visited.length ; s ++) {
					//只有已读的节点可以用来遍历,查找它的邻接最短路径
					if (visited[s] == 1) {
						//循环该节点的所有邻接节点
						for (int i = 0; i < verx; i++) {
							//当节点连通并且连通的该节点是未读状态时
							if (weight[s][i] != 0 && visited[i] == 0) {
								//验证该路径是否是最小路径,当是较小的路径时记录该路径的X(起始点)和Y(结束点)坐标
								if (minX == -1 || weight[minX][minY] > weight[s][i]) {
									minX = s;
									minY = i;
								}
							}
						}
					}
				}
				//退出循环min指向最小路径的下标,将该节点的读取状态设置为已读
				visited[minY] = 1;
				//打印最小路径
				System.out.println(data[minX] + " -> " + data[minY] + " : " + weight[minX][minY]);
				//将最小路径设置为邻接矩阵,用于生成新的图
				newGraph[minX][minY] = weight[minX][minY];
			}
			//返回一个新的图
			return new MGraph(verx,data,newGraph);
		}
		
		//=========================克鲁斯卡尔算法生成最小路径图===========================
		//首先编写方法,对图中的路径排序
		public List<Map<String, Integer>> order(){
			//获取所有的边
			List<Map<String, Integer>> edge = new ArrayList<>();
			for (int a = 0 ; a < weight.length ; a ++){
				for (int b = a + 1 ; b < weight[0].length ; b ++){
					if (weight[a][b] > 0){
						Map<String, Integer> ed = new HashMap<>();
						ed.put("start",a);
						ed.put("end",b);
						ed.put("len",weight[a][b]);
						edge.add(ed);
					}
				}
			}
			//按照边的权值进行排序
			edge.sort((a,b) -> Integer.compare((int)a.get("len"),(int)b.get("len")));
			return edge;
		}
		
		//根据传入的节点获取它的终点
		/*
		 * 自己实现的获取终点的方法:
		 * 在这里的实现思路是,根据传入的节点和索引图,查找对应节点的那一行数据,获取到最大的邻接节点,
		 * 拿最大的邻接节点再到对应的数据行中找到它对应的最大临接节点,以此不断递归,直到某行数据都为0时
		 * 就得到了它的最终终点,同样在createKruskalMinGraph()方法中,同样需要对该边的起始节点的最终节点设置它的最终节点
		 */
		public int getEnd(int v,int[][] select){
			int index = -1;
			for (int b = select.length - 1 ; b >= 0 ; b --){
				if(select[v][b] != 0){
					index = b;
					break;
				}
			}
			if (index != -1){
				return getEnd(index,select);
			}else{
				return v;
			}
		}
		
		//克鲁斯卡尔算法生成最小路径图,自己实现的算法
		public void createKruskalMinGraph(){
			//创建一个选中的图
			int[][] select = new int[verx][verx];
			//首先对边进行排序
			List<Map<String, Integer>> orderEdge = order();
			//从边集合中顺序获取边
			for (Map<String, Integer> edge : orderEdge) {
				int start = edge.get("start");
				int end = edge.get("end");
				//获取两个节点的最终节点
				int m = getEnd(start, select);
				int n = getEnd(end, select);
				//验证是否形成回路
				if (m != n){
					//没有形成回路,则将得到的最终节点赋值为-1,表示最终节点已变更
					select[m][n] = -1;
					System.out.println(data[start] + " -> " + data[end] + " :" + weight[start][end]);
				}
			}
			
		}
		
		//查找终点:标准方法
		//在这里去查找时会不断的去找它终点的终点,直到找到一个未设置终点的节点,这个节点就是终点
		//同样在createKruskalMinGraph1()方法中对ends数组设置终点时同样也是给这个起始节点的最终终点设置的终点,如此才能获得最终节点
		private int getEnd1(int i,int[] ends){
			while (ends[i] != 0){
				i = ends[i];
			}
			return i;
		}
		
		//克鲁斯卡尔算法生成最小路径图:标准算法
		public void createKruskalMinGraph1(){
			//创建终点数组
			int[] ends = new int[verx];
			//首先对边进行排序
			List<Map<String, Integer>> orderEdge = order();
			//从边集合中顺序获取边
			for (Map<String, Integer> edge : orderEdge) {
				int start = edge.get("start");
				int end = edge.get("end");
				//获取节点的终点
				int send = getEnd1(start, ends);
				int eend = getEnd1(end, ends);
				//判断是否形成回路
				if (send != eend) {
					//如果没有形成回路,对上面找到的起始节点的终点,设置终点
					ends[send] = eend;
					System.out.println(data[start] + " -> " + data[end] + " :" + weight[start][end]);
				}
			}
		}
	}
}
